“PHASETRANS” STARTPAGE HUMAN RESOURCES AND MOBILITY (HRM) ACTIVITY

The theory of NP-completeness [GJ79] is arguably the most important intellectual contribution of Theoretical Computer Science to general scientific knowledge. Thousands of NP-complete problems are known, in scientific areas as diverse as protein folding, statistical physics, or computational social sciences. NP completeness is an indicator of computational intractability, since the computational time of all known algorithms (and indeed all algorithms, assuming that the famous conjecture P ≠ NP is true) scales superpolynomially with instance size. Despite this success, the concept of an NP-complete problem does not completely model experimental reality: the problem is that NP-completeness is a worst-case concept, so any NP-complete problem contains some ”hard ” instances. But the theory does not address the issue of ”density ” of such hard instances, and indeed, NP-complete problems can differ significantly with respect to the computational difficulty of ”typical ” instances arising in practice. Recent years have witnessed the emergence of a new field of research, at the crossroads of Statistical Physics, Theoretical Computer Science and Artificial Intelligence: the study of phase transitions in combinatorial problems [PIM06]. This remarkable development has generated substantial excitement in the scientific [GS05, Rob05] and the popular press [Joh99, Hay97, Hay03]. Concepts from the physics of spin glasses, such as first-order phase transitions, backbones, or the replica method ofte